package acwing;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q002_数字三角形 {
    public static void main(String[] args) {

    }

    public void func1() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] dp = new int[n][n];
        int[][] w = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                w[i][j] = sc.nextInt();
            }
        }
        for (int j = 0; j < n; j++) {
            dp[n-1][j] = w[n-1][j];
        }
        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j+1]) + w[i][j];
            }
        }
        System.out.print(dp[0][0]);
    }

    // 优化空间
    public void func2() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = sc.nextInt();
            }
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] += Math.max(dp[i+1][j],dp[i+1][j+1]);
            }
        }
        System.out.println(dp[0][0]);
    }
}
